//给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 
//
// 你的算法时间复杂度必须是 O(log n) 级别。 
//
// 如果数组中不存在目标值，返回 [-1, -1]。 
//
// 示例 1: 
//
// 输入: nums = [5,7,7,8,8,10], target = 8
//输出: [3,4] 
//
// 示例 2: 
//
// 输入: nums = [5,7,7,8,8,10], target = 6
//输出: [-1,-1] 
// Related Topics 数组 二分查找 
// 👍 568 👎 0

package leetcode.editor.cn;

//Java：在排序数组中查找元素的第一个和最后一个位置
public class P34FindFirstAndLastPositionOfElementInSortedArray {

    //leetcode submit region begin(Prohibit modification and deletion)
    /**
     *
     * 思路：二分法，但是第一次命中之后要保存现场，然后再循环命中的左部，找到又一次命中下标的最小的，然后再循环命中的右部，找到又一次命中下标的最大的
     *
     *
     * 执行用时： 0 ms , 在所有 Java 提交中击败了 100.00% 的用户 内存消耗： 43.1 MB , 在所有 Java 提交中击败了 40.90% 的用户
     *
     */

    //  5,7,4,3,8,8,8,8,10
    // 1,2,2,2,3,3,5,5,5,5,5,5,7,7,7,8,8,9,9
    class Solution {
        public int[] searchRange(int[] nums, int target) {
            int start = -1;         // 目标值 开始位置
            int end = -1;           // 目标值 结束位置

            int left = 0;               // 循环的左下标
            int right = nums.length - 1;    // 循环的右下标

            int firstMid = -1;          // 第一次命中的mid值
            int firstLeft = -1;         // 第一次命中的left值
            int firstRight = -1;        // 第一次命中的right值
            boolean loopLeft = false;   // 用两个boolean 值，来控制循环  为true则循环左部
            boolean loopRight = false;  // 用两个boolean 值，来控制循环  为true则循环右部

            while (true) {
                while (left <= right) {
                    int mid = (left + right) / 2;
                    if (nums[mid] < target) {
                        left = mid + 1;
                    } else if (nums[mid] > target) {
                        right = mid - 1;
                    } else {
                        // 相等
                        if (loopLeft) {
                            start = mid;
                            right = mid - 1;
                        } else if (loopRight) {
                            end = mid;
                            left = mid + 1;
                        } else {
                            start = mid;
                            end = mid;
                            firstMid = mid;
                            firstLeft = left;
                            firstRight = right;
                            break;
                        }
                    }
                }
                if (firstMid == -1 || loopRight) {
                    break;
                }

                // 一开始循环左边，然后循环右边
                if (!loopLeft) {
                    loopLeft = true;
                    left = firstLeft;
                    right = firstMid - 1;
                } else {
                    loopLeft = false;
                    loopRight = true;
                    left = firstMid + 1;
                    right = firstRight;
                }
            }
            return new int[]{start, end};
        }
    }

    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P34FindFirstAndLastPositionOfElementInSortedArray().new Solution();
        int[] nums = new int[]{};
        int[] result = solution.searchRange(nums, 1);
        System.out.println(result[0] + " " + result[1]);
        // TO TEST
    }

}